from collections import deque

def pacificAtlantic(matrix: list[list[int]]) -> list[list[int]]:
    if not matrix:
        return []
    
    m, n = len(matrix), len(matrix[0])
    
    # 这两个数组记录是否能够到达太平洋和大西洋
    pacific_visited = [[False] * n for _ in range(m)]
    atlantic_visited = [[False] * n for _ in range(m)]
    
    # 初始化队列
    pacific = deque()
    atlantic = deque()
    
    # 从太平洋的边界初始化队列
    for i in range(m):
        pacific.append((i, 0))  # 太平洋的第一列
        pacific_visited[i][0] = True
    for j in range(n):
        pacific.append((0, j))  # 太平洋的第一行
        pacific_visited[0][j] = True
    
    # 从大西洋的边界初始化队列
    for i in range(m):
        atlantic.append((i, n - 1))  # 大西洋的最后一列
        atlantic_visited[i][n - 1] = True
    for j in range(n):
        atlantic.append((m - 1, j))  # 大西洋的最后一行
        atlantic_visited[m - 1][j] = True

    # DFS函数，遍历可以到达的区域
    def bfs(queue, visited, other_visited):
        while queue:
            x, y = queue.popleft()
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and matrix[nx][ny] >= matrix[x][y]:
                    visited[nx][ny] = True
                    queue.append((nx, ny))

    # 对太平洋和大西洋分别进行 BFS
    bfs(pacific, pacific_visited, atlantic_visited)
    bfs(atlantic, atlantic_visited, pacific_visited)
    
    # 找到两个海洋都可以到达的格子
    result = []
    for i in range(m):
        for j in range(n):
            if pacific_visited[i][j] and atlantic_visited[i][j]:
                result.append([i, j])

    return result

if __name__ == "__main__":
    matrix = [
        [1, 2, 2, 3, 5],
        [3, 2, 3, 4, 4],
        [2, 4, 5, 3, 1],
        [6, 7, 1, 4, 2],
        [5, 1, 1, 2, 4]
    ]
    print(pacificAtlantic(matrix))  # 输出符合条件的坐标列表
